package com.hiwhitley.easy.day24;

/**
 * Created by hiwhitley on 2016/10/16.
 */
public class CountingBits_338 {
    /**
     *  [2,3]->[1,2], [4,7]->[1,2,2,3], [8-15]->[1,2,2,3,2,3,3,4]，
     *  新的范围是上一个区间再加上上一个区间每个元素+1的结果，
     * @param num
     * @return
     */
    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        res[0] = 0;
        int base = 1;
        while (base <= num) {
            int next = base * 2;
            for (int i = base ; i< next && i <= num; i++) {
                res[i] = res[i-base] + 1;
            }
            base = next;
        }

        return res;
    }

    public static void main(String[] args) {
        CountingBits_338 main = new CountingBits_338();
        System.out.println(main.countBits(5));
    }
}
